package practice_2025_7_24;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    /**
     * 最长等差数列
     * 超时
     * @param nums
     * @return
     */
    public int longestArithSeqLength1(int[] nums) {
        // 计算最长等差子序列的长度
        // dp[i][j]: 以 nums[i], nums[j] 为结尾的最长等差子序列长度, 公差 nums[j] - nums[i]
        // 再遍历 0 - nums[i] 之间元素k, 计算 dp[i][j] = max(dp[i][j], dp[k][i] + 1)
        // 初始化: 
        int n = nums.length;
        int[][] dp = new int[n][n];
        int max = 0;
        // 初始化
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                dp[i][j] = 2;
            }
        }
        dp[0][0] = 1;
        for(int j = 1; j < n; j++) {
            for(int i = 0; i < j; i++) {
                int d = nums[j] - nums[i];
                for(int k = 0; k < i; k++) {
                    if (nums[i] - nums[k] == d) {
                        dp[i][j] = Math.max(dp[i][j], dp[k][i] + 1);
                    } 
                }
                max = Math.max(dp[i][j], max);
            }
        }
        return max;
    }

    /**
     * 使用 哈希表 进行优化
     * @param nums
     * @return
     */
    public int longestArithSeqLength(int[] nums) {
        // 计算最长等差子序列的长度
        // dp[i][j]: 以 nums[i], nums[j] 为结尾的最长等差子序列长度, 公差 nums[j] - nums[i]
        // 再遍历 0 - nums[i] 之间元素k, 计算 dp[i][j] = max(dp[i][j], dp[k][i] + 1)
        // nums[i] * = nums[j] + nums[k]
        int n = nums.length;
        int[][] dp = new int[n][n];
        Map<Integer, Integer> hash = new HashMap<>(); // k -> index
        int max = 2;
        // 初始化
        for(int i = 0; i < n; i++) {
            for(int j = i + 1; j < n; j++) {
                dp[i][j] = 2;
            }
        }
        hash.put(nums[0], 0);
        for(int i = 1; i < n - 1; i++) {
            for(int j = i + 1; j < n; j++) {
                int k = nums[i] * 2 - nums[j];
                if (hash.containsKey(k)) {
                    int indexK = hash.get(k);
                    dp[i][j] = Math.max(dp[i][j], dp[indexK][i] + 1);
                    // System.out.println("key: " + k + " " + indexK);
                    // System.out.println(max + " " + " " + i + " " + j);
                    max = Math.max(dp[i][j], max);
                }
            }
            hash.put(nums[i], i);
        }
        return max;
    }

    /**
     * 等差数列划分II —— 子序列
     * @param nums
     * @return
     */
    public int numberOfArithmeticSlices(int[] nums) {
        // 返回 nums 中 等差数列的个数
        // dp[i][j]: 以 nums[i], nums[j] 为结尾的等差数量个数
        // nums[k] = nums[i] * 2 - nums[j]
        // dp[i][j] += (dp[k][i] + 1)
        int n = nums.length;
        int[][] dp = new int[n][n];
        Map<Long, List<Integer>> hash = new HashMap<>();
        int count = 0;
        for(int i = 0; i < n; i++) {
            for(int j = i + 1; j < n; j++) {
                long k = (long)nums[i] * 2 - nums[j];
                if (hash.containsKey(k)) {
                    List<Integer> tmp = hash.getOrDefault(k, null);
                    if (tmp != null) {
                        for(int t = 0; t < tmp.size(); t++) {
                            dp[i][j] += (dp[tmp.get(t)][i] + 1);
                        }
                    } else {
                        dp[i][j] = 1;
                    }
                    count += dp[i][j];
                }
            }
            List<Integer> list = hash.getOrDefault((long)nums[i], new ArrayList<>());
            list.add(i);
            hash.put((long)(nums[i]), list);
        }
        return count;
    }
}